{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Path Cost in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minPathCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格中的最小路径代价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数矩阵&nbsp;<code>grid</code> ，矩阵大小为 <code>m x n</code> ，由从 <code>0</code> 到 <code>m * n - 1</code> 的不同整数组成。你可以在此矩阵中，从一个单元格移动到 <strong>下一行</strong> 的任何其他单元格。如果你位于单元格 <code>(x, y)</code> ，且满足 <code>x &lt; m - 1</code> ，你可以移动到 <code>(x + 1, 0)</code>, <code>(x + 1, 1)</code>, ..., <code>(x + 1, n - 1)</code><strong> </strong>中的任何一个单元格。<strong>注意：</strong>&nbsp;在最后一行中的单元格不能触发移动。</p>\n",
    "\n",
    "<p>每次可能的移动都需要付出对应的代价，代价用一个下标从 <strong>0</strong> 开始的二维数组 <code>moveCost</code> 表示，该数组大小为 <code>(m * n) x n</code> ，其中 <code>moveCost[i][j]</code> 是从值为 <code>i</code> 的单元格移动到下一行第 <code>j</code> 列单元格的代价。从&nbsp;<code>grid</code> 最后一行的单元格移动的代价可以忽略。</p>\n",
    "\n",
    "<p><code>grid</code> 一条路径的代价是：所有路径经过的单元格的 <strong>值之和</strong> 加上 所有移动的 <strong>代价之和 </strong>。从 <strong>第一行</strong> 任意单元格出发，返回到达 <strong>最后一行</strong> 任意单元格的最小路径代价<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/28/griddrawio-2.png\" style=\"width: 301px; height: 281px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>最小代价的路径是 5 -&gt; 0 -&gt; 1 。\n",
    "- 路径途经单元格值之和 5 + 0 + 1 = 6 。\n",
    "- 从 5 移动到 0 的代价为 3 。\n",
    "- 从 0 移动到 1 的代价为 8 。\n",
    "路径总代价为 6 + 3 + 8 = 17 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "最小代价的路径是 2 -&gt; 3 。 \n",
    "- 路径途经单元格值之和 2 + 3 = 5 。 \n",
    "- 从 2 移动到 3 的代价为 1 。 \n",
    "路径总代价为 5 + 1 = 6 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>grid</code> 由从 <code>0</code> 到 <code>m * n - 1</code> 的不同整数组成</li>\n",
    "\t<li><code>moveCost.length == m * n</code></li>\n",
    "\t<li><code>moveCost[i].length == n</code></li>\n",
    "\t<li><code>1 &lt;= moveCost[i][j] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-path-cost-in-a-grid](https://leetcode.cn/problems/minimum-path-cost-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-path-cost-in-a-grid](https://leetcode.cn/problems/minimum-path-cost-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[5,3],[4,0],[2,1]]\\n[[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]', '[[5,1,2],[4,0,3]]\\n[[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            if x == m - 1:\n",
    "                return grid[x][y]\n",
    "            res = inf\n",
    "            for j in range(n):\n",
    "                res = min(res, moveCost[grid[x][y]][j] + grid[x][y] + dfs(x + 1, j))\n",
    "            return res\n",
    "\n",
    "        ans = min(dfs(0, j) for j in range(n))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_val = float(\"inf\")\n",
    "        dp = [[max_val]*n for _ in range(m)]\n",
    "\n",
    "        for j in range(n):\n",
    "            dp[0][j] = grid[0][j]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for x in range(n):\n",
    "                    num = grid[i-1][x]\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][x]+moveCost[num][j])\n",
    "                dp[i][j] = dp[i][j] + grid[i][j]\n",
    "\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = grid[0]\n",
    "        for i in range(1, len(grid)):\n",
    "            dp = [grid[i][j] + min(dp[k] + moveCost[grid[i - 1][k]][j] for k in range(n)) for j in range(n)]\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        MAX = int(1e9)\n",
    "        path_cost = grid[0]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m-1):\n",
    "            new_cost = [MAX] * n\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    new_cost[k] = min(new_cost[k], path_cost[j] + moveCost[grid[i][j]][k])\n",
    "        \n",
    "            for j in range(n):\n",
    "                # adding base\n",
    "                path_cost[j] = new_cost[j] + grid[i+1][j]\n",
    "        return min(path_cost)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n):\n",
    "                grid[i][j] += min(g + c for g, c in zip(grid[i + 1], moveCost[grid[i][j]]))\n",
    "        return min(grid[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[float('inf')] * n for _ in range(m)]\n",
    "        for i in range(n): dp[0][i] = grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + moveCost[grid[i - 1][k]][j] + grid[i][j])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "#记dp[i][j]为到达最后一行的最小代价，dp[i][j]=grid[i][j]+min(dp[i+1][0]+moveCost[grid[i][j]][0],dp[i+1][1]+moveCost[grid[i][j]][1],...,dp[i+1][n-1])+moveCost[grid[i][j]][n-1])\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[0]*n for _ in range(0,m)]\n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                if i==0:\n",
    "                    dp[m-1-i][j]=grid[m-1-i][j]\n",
    "                else:\n",
    "                    tmp = dp[m-i][0]+moveCost[grid[m-1-i][j]][0]\n",
    "                    for k in range(1,n):\n",
    "                        tmp = min(tmp,dp[m-i][k]+moveCost[grid[m-1-i][j]][k])\n",
    "                    dp[m-1-i][j]=grid[m-1-i][j]+tmp                \n",
    "        return(min(dp[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [0] * n\n",
    "        for i, v in enumerate(grid[0]):\n",
    "            dp[i] = v\n",
    "        for i in range(1, m):\n",
    "            nex = dp[:]\n",
    "            for j in range(n):\n",
    "                nex[j] = min(dp[k] + moveCost[grid[i - 1][k]][j] + grid[i][j] for k in range(n))\n",
    "            dp = nex\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        # greedy dp\n",
    "        temp = [item for item in grid[0]]\n",
    "        for i in range(1, len(grid)):\n",
    "            new_temp = [float('inf')] * len(grid[0])\n",
    "            for j in range(len(grid[0])):\n",
    "                for k in range(len(grid[0])):\n",
    "                    new_temp[k] = min(temp[j] + moveCost[grid[i - 1][j]][k] + grid[i][k], new_temp[k])\n",
    "            temp = new_temp\n",
    "        return min(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [num for num in grid[0]]\n",
    "        for i in range(1, m):\n",
    "            tmp = [0xffffffff] * n\n",
    "            for k in range(n):\n",
    "                for j in range(n):\n",
    "                    tmp[k] = min(tmp[k],  dp[j] + moveCost[grid[i - 1][j]][k] + grid[i][k])\n",
    "            dp = tmp\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = grid[0]\n",
    "        for i in range(1, m):\n",
    "            dp = [grid[i][j] + min(dp[k] + moveCost[grid[i-1][k]][j] for k in range(n)) for j in range(n)]\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = grid[0]\n",
    "        for i in range(1, len(grid)):\n",
    "            dp = [grid[i][j] + min(dp[k] + moveCost[grid[i - 1][k]][j] for k in range(n)) for j in range(n)]\n",
    "\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        sol = grid[-1]\n",
    "        for i in range(len(grid)-2,-1,-1):\n",
    "            new = []\n",
    "            for j in range(len(sol)):\n",
    "                curr = grid[i][j]\n",
    "                cost = min([moveCost[curr][k]+sol[k] for k in range(len(sol))])\n",
    "                new.append(curr+cost)\n",
    "            sol = new\n",
    "        return min(sol)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[inf] * n for _ in range(m)] #dp[i][j]表示从第i行第j列出发应该付出的最小代价\n",
    "        dp[-1] = grid[-1]\n",
    "        \n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j, g in enumerate(grid[i]):\n",
    "                for k, c in enumerate(moveCost[g]):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i + 1][k] + c)\n",
    "                dp[i][j] += g\n",
    "        return min(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        dp = [[float('inf') for _ in range(n)] for _ in range(m)]\n",
    "        dp[0] = grid[0]\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    dp[i][j] = min(dp[i-1][k]+moveCost[grid[i-1][k]][j],dp[i][j])\n",
    "                dp[i][j] += grid[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp = [[float('inf')] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[0][i] = grid[0][i]\n",
    "            \n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    \n",
    "                    dp[i][j] = min(grid[i][j] + dp[i-1][k] + moveCost[grid[i-1][k]][j], dp[i][j])\n",
    "\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[float('inf')]*n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[0][j]=grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    cost=dp[i-1][k]+moveCost[grid[i-1][k]][j]+grid[i][j]\n",
    "                    dp[i][j]=min(dp[i][j],cost)\n",
    "        return min(dp[-1])            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        dp = [[inf]*len(grid[0]) for i in range(len(grid))]\n",
    "        for i in range(len(grid)-1, -1, -1):\n",
    "            if i == len(grid) - 1:\n",
    "                dp[i] = grid[i]\n",
    "            else:\n",
    "                for j in range(len(grid[i])):\n",
    "                    for k in range(len(moveCost[grid[i][j]])):\n",
    "                        dp[i][j] = min(grid[i][j] + moveCost[grid[i][j]][k] + dp[i+1][k], dp[i][j])\n",
    "                        \n",
    "        return min(dp[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        ans = [[0 for a in range(len(grid[0]))] for b in range(len(grid))]\n",
    "        for number in range(len(grid[0])):\n",
    "            ans[0][number] = grid[0][number]\n",
    "        for x in range(1,len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                min = 10000000000000000000000000000000\n",
    "                for i in range(len(grid[0])):\n",
    "                    compare = ans[x-1][i] + grid[x][y] + moveCost[grid[x-1][i]][y]\n",
    "                    if compare < min:\n",
    "                        min = compare\n",
    "                ans[x][y] = min\n",
    "        min = 1000000000000\n",
    "        for j in range(len(grid[0])):\n",
    "            if ans[len(grid)-1][j] < min:\n",
    "                min = ans[len(grid)-1][j]\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[inf] * n for _ in range(m)]\n",
    "        f[-1] = grid[-1]\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j, g in enumerate(grid[i]):\n",
    "                for k, c in enumerate(moveCost[g]):  # 移动到下一行的第 k 列\n",
    "                    f[i][j] = min(f[i][j], f[i + 1][k] + c)\n",
    "                f[i][j] += g\n",
    "        return min(f[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        new_num = [0 for _ in range(n)]\n",
    "        for i in range(m-1, 0, -1):\n",
    "            for j in range(n):\n",
    "                up_grid = grid[i-1][j]\n",
    "                down_grid = moveCost[up_grid][0] + grid[i][0]\n",
    "                for z in range(1, n):\n",
    "                    if moveCost[up_grid][z] + grid[i][z] < down_grid:\n",
    "                        down_grid = moveCost[up_grid][z] + grid[i][z]\n",
    "                grid[i-1][j] = down_grid + up_grid\n",
    "        return min(grid[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[inf] * n for _ in range(m)]\n",
    "        f[-1] = grid[-1]\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j, g in enumerate(grid[i]):\n",
    "                for k, c in enumerate(moveCost[g]):  # 移动到下一行的第 k 列\n",
    "                    f[i][j] = min(f[i][j], f[i + 1][k] + c)\n",
    "                f[i][j] += g\n",
    "        return min(f[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[inf] * n for _ in range(m)]\n",
    "        f[-1] = grid[-1]\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j, g in enumerate(grid[i]):\n",
    "                for k, c in enumerate(moveCost[g]):  # 移动到下一行的第 k 列\n",
    "                    f[i][j] = min(f[i][j], f[i + 1][k] + c)\n",
    "                f[i][j] += g\n",
    "        return min(f[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "\n",
    "        m = grid.__len__()\n",
    "        n = grid[0].__len__()\n",
    "\n",
    "        mx = 1000000000 + 7\n",
    "        dp = [[mx] * n for _ in range(m)]\n",
    "\n",
    "        for j in range(n):\n",
    "            dp[0][j] = grid[0][j]\n",
    "\n",
    "        for i in range(m - 1):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + moveCost[grid[i][j]][k] + grid[i + 1][k])\n",
    "\n",
    "        ans = dp[m - 1][0]\n",
    "        for k in range(n):\n",
    "            ans = min(ans, dp[m - 1][k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        dp = grid[0].copy()\n",
    "        for i in range(rows - 1):\n",
    "            tmp = [sys.maxsize]*cols\n",
    "            for j in range(cols):\n",
    "                for m in range(cols):\n",
    "                    tmp[m] = min(tmp[m], dp[j] + moveCost[grid[i][j]][m] + grid[i+1][m])\n",
    "            dp = tmp\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n):\n",
    "                grid[i][j] += min(g + c for g, c in zip(grid[i + 1], moveCost[grid[i][j]]))\n",
    "        return min(grid[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[float('inf')]*n for _ in range(m)]  # 从 第一行 任意单元格出发，到达每个节点的最小代价\n",
    "        dp[0] =  grid[0]\n",
    "        for row in range(1, m):\n",
    "            for col in range(n):\n",
    "                for k in range(n):\n",
    "                    dp[row][col] = min(dp[row][col], grid[row][col] + dp[row-1][k] + moveCost[grid[row-1][k]][col])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = grid[0]\n",
    "        for i in range(1, len(grid)):\n",
    "            dp = [grid[i][j] + min(dp[k] + moveCost[grid[i - 1][k]][j] for k in range(n)) for j in range(n)]\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cost = [[float('inf')] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            cost[0][j] = grid[0][j]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    cost[i][j] = min(cost[i][j], grid[i][j] + cost[i - 1][k] + moveCost[grid[i - 1][k]][j])\n",
    "        return min(cost[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = grid[0]\n",
    "        for i in range(1, m):\n",
    "            g = [inf] * n\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    g[j] = min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j])\n",
    "            f = g\n",
    "        return min(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[math.inf]*n for i in range(m)]\n",
    "        dp[0] = grid[0]\n",
    "        for i in range(0, m - 1):\n",
    "            for j in range(0, n):\n",
    "                for k in range(0, n):\n",
    "                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + moveCost[grid[i][j]][k] + grid[i+1][k])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # we need a list to track the cost of getting to certain index a t current row\n",
    "    # use this and the move cost to get the cost of getting to next row\n",
    "    # return the minimal cost\n",
    "    # start from row 0, cost is 0\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m = len(grid[0]) # col num\n",
    "        n = len(grid) # row num\n",
    "        costs = grid[0]\n",
    "        for i in range(1,n):\n",
    "            temp = [99999] * len(grid[0])\n",
    "            for j in range(0,m): # to j\n",
    "                for k in range(0, m): # from k\n",
    "                    temp[j] = min(temp[j], costs[k] + grid[i][j] + moveCost[grid[i-1][k]][j])\n",
    "            costs = temp\n",
    "        return min(costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        ans = [[0 for a in range(len(grid[0]))] for b in range(len(grid))]\n",
    "        for number in range(len(grid[0])):\n",
    "            ans[0][number] = grid[0][number]\n",
    "        for x in range(1,len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                min = 10000000000000000000000000000000\n",
    "                for i in range(len(grid[0])):\n",
    "                    compare = ans[x-1][i] + grid[x][y] + moveCost[grid[x-1][i]][y]\n",
    "                    if compare < min:\n",
    "                        min = compare\n",
    "                ans[x][y] = min\n",
    "        min = 1000000000000\n",
    "        for j in range(len(grid[0])):\n",
    "            if ans[len(grid)-1][j] < min:\n",
    "                min = ans[len(grid)-1][j]\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[inf] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = grid[0][j]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][k] + moveCost[grid[i-1][k]][j] + grid[i][j])\n",
    "        return min(dp[m-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # dp = [[math.inf]*n for i in range(m)]\n",
    "        # dp[0] = grid[0]\n",
    "        dp = grid[0]\n",
    "        for i in range(0, m - 1):\n",
    "            new_dp = [math.inf]*n\n",
    "            for j in range(0, n):\n",
    "                for k in range(0, n):\n",
    "                    new_dp[k] = min(new_dp[k], dp[j] + moveCost[grid[i][j]][k] + grid[i+1][k])\n",
    "            dp = new_dp\n",
    "        return min(dp)\n",
    "# class Solution:\n",
    "#     def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "#         @cache\n",
    "#         def dfs(i: int, j: int) -> int:\n",
    "#             return grid[i][j] if i == 0 else min(dfs(i - 1, k) + moveCost[grid[i - 1][k]][j] + grid[i][j] for k in range(len(grid[0])))\n",
    "#         return min(dfs(len(grid) - 1, j) for j in range(len(grid[0])))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "#         m = len(grid)\n",
    "#         n = len(grid[0])\n",
    "#         dp = [[math.inf]*n for i in range(m)]\n",
    "#         dp[0] = grid[0]\n",
    "#         for i in range(0, m - 1):\n",
    "#             for j in range(0, n):\n",
    "#                 for k in range(0, n):\n",
    "#                     dp[i+1][k] = min(dp[i+1][k], dp[i][j] + moveCost[grid[i][j]][k] + grid[i+1][k])\n",
    "#         return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        @cache\n",
    "        def dfs(x,i):\n",
    "            res = inf\n",
    "            if i == n - 1:\n",
    "                return x\n",
    "            for j,y in enumerate(grid[i + 1]):\n",
    "                res = min(res,x + moveCost[x][j] + dfs(y,i + 1))\n",
    "            return res\n",
    "        for x in grid[0]:\n",
    "            ans = min(ans,dfs(x,0))\n",
    "        return ans\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        ans = [[0 for a in range(len(grid[0]))] for b in range(len(grid))]\n",
    "        for number in range(len(grid[0])):\n",
    "            ans[0][number] = grid[0][number]\n",
    "        for x in range(1,len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                min = 10000000000000000000000000000000\n",
    "                for i in range(len(grid[0])):\n",
    "                    compare = ans[x-1][i] + grid[x][y] + moveCost[grid[x-1][i]][y]\n",
    "                    if compare < min:\n",
    "                        min = compare\n",
    "                ans[x][y] = min\n",
    "        min = 1000000000000\n",
    "        for j in range(len(grid[0])):\n",
    "            if ans[len(grid)-1][j] < min:\n",
    "                min = ans[len(grid)-1][j]\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 会超时的递归代码\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == m - 1:  # 递归边界\n",
    "                return grid[i][j]\n",
    "            res = inf\n",
    "            for k, c in enumerate(moveCost[grid[i][j]]):  # 移动到下一行的第 k 列\n",
    "                res = min(res, dfs(i + 1, k) + c)\n",
    "            return res + grid[i][j]\n",
    "\n",
    "        return min(dfs(0, j) for j in range(n))  # 枚举起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    \n",
    "    def minPathCost(self, grid:list, moveCost) -> int:\n",
    "        point_nums = len(grid) * len(grid[0])\n",
    "        grid.insert(0,[point_nums])\n",
    "        # point_nums -> start\n",
    "        grid.append([point_nums + 1])\n",
    "        # point_nums + 1 -> end\n",
    "        level_dic = {}\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                level_dic[grid[i][j]] = i\n",
    "        \n",
    "        for i in range(len(grid[-2])):\n",
    "            moveCost[grid[-2][i]] = [0]\n",
    "        moveCost.append([0 for _ in range(len(grid[1]))])\n",
    "        in_queue = [0 for _ in range(point_nums + 2)]\n",
    "        cost = [float('inf') for _ in range(point_nums + 2)]\n",
    "        cost[point_nums] = 0\n",
    "        queue = deque()\n",
    "        queue.append(point_nums)\n",
    "        in_queue[point_nums] = 1\n",
    "        while(queue):\n",
    "            p = queue.popleft()\n",
    "            in_queue[p] = 0\n",
    "            if p == point_nums + 1:\n",
    "                continue\n",
    "            for i in range(len(grid[level_dic[p] + 1])):\n",
    "                next_p = grid[level_dic[p] + 1][i]\n",
    "                cmp = cost[p] + moveCost[p][i] + p\n",
    "                if cmp < cost[next_p]:\n",
    "                    cost[next_p] = cmp\n",
    "                    if in_queue[next_p] == 0:\n",
    "                        in_queue[next_p] = 1\n",
    "                        queue.append(next_p)\n",
    "        return cost[point_nums + 1] - point_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minPathCost(self, grid, moveCost):\n",
    "        m, n, INF = len(grid), len(grid[0]), float('inf')\n",
    "        ans = INF\n",
    "        dist = [[INF] * n for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            dist[0][i] = grid[0][i]\n",
    "        pq = [(0, i, grid[0][i]) for i in range(n)]\n",
    "        while pq:\n",
    "            x, y, cur = heapq.heappop(pq)\n",
    "            if x == m - 1:\n",
    "                ans = min(ans, cur)\n",
    "                continue\n",
    "            for i in range(n):\n",
    "                step, ne = moveCost[grid[x][y]][i], grid[x + 1][i]\n",
    "                tot = cur + step + ne\n",
    "                if tot >= ans or dist[x + 1][i] <= tot: continue\n",
    "                dist[x + 1][i] = tot\n",
    "                heapq.heappush(pq, (x + 1, i, tot))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        ans = [[0 for a in range(len(grid[0]))] for b in range(len(grid))]\n",
    "        for number in range(len(grid[0])):\n",
    "            ans[0][number] = grid[0][number]\n",
    "        for x in range(1,len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                min = 10000000000000000000000000000000\n",
    "                for i in range(len(grid[0])):\n",
    "                    compare = ans[x-1][i] + grid[x][y] + moveCost[grid[x-1][i]][y]\n",
    "                    if compare < min:\n",
    "                        min = compare\n",
    "                ans[x][y] = min\n",
    "        min = 1000000000000\n",
    "        for j in range(len(grid[0])):\n",
    "            if ans[len(grid)-1][j] < min:\n",
    "                min = ans[len(grid)-1][j]\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i, j) -> int:\n",
    "            if i == m - 1:\n",
    "                return grid[i][j]\n",
    "            res = inf\n",
    "            for k, c in enumerate(moveCost[grid[i][j]]):\n",
    "                res = min(res, dfs(i + 1, k) + c)\n",
    "            return res + grid[i][j]\n",
    "        return min(dfs(0, j) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    \n",
    "    def minPathCost(self, grid:list, moveCost) -> int:\n",
    "        point_nums = len(grid) * len(grid[0])\n",
    "        grid.insert(0,[point_nums])\n",
    "        # point_nums -> start\n",
    "        grid.append([point_nums + 1])\n",
    "        # point_nums + 1 -> end\n",
    "        \"\"\"\n",
    "        for i in range(len(moveCost)):\n",
    "            for j in range(len(moveCost[0])):\n",
    "                moveCost[i][j] += i\n",
    "        \"\"\"\n",
    "        for i in range(len(grid[-2])):\n",
    "            moveCost[grid[-2][i]] = [grid[-2][i]]\n",
    "        moveCost.append([0 for _ in range(len(grid[1]))])\n",
    "        level_dic = {}\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                level_dic[grid[i][j]] = i\n",
    "        cost = [float('inf') for _ in range(point_nums + 2)]\n",
    "        cost[point_nums] = 0\n",
    "        S = set()\n",
    "        pac = [(0, point_nums)]\n",
    "        while(True):\n",
    "            length, p = heapq.heappop(pac)\n",
    "            if length > cost[p] or p in S:\n",
    "                continue\n",
    "            if p == point_nums + 1:\n",
    "                break\n",
    "            for i in range(len(grid[level_dic[p] + 1])):\n",
    "                child_p = grid[level_dic[p] + 1][i]\n",
    "                if child_p not in S:\n",
    "                    if child_p ==  point_nums + 1:\n",
    "                        cost[child_p] = min(cost[child_p], cost[p] + moveCost[p][i])\n",
    "                    else:\n",
    "                        cost[child_p] = min(cost[child_p], cost[p] + moveCost[p][i] + p)\n",
    "                    heapq.heappush(pac, (cost[child_p], child_p))\n",
    "\n",
    "            S.add(p)\n",
    "\n",
    "        return cost[p] - point_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            return grid[i][j] if i == 0 else min(dfs(i - 1, k) + moveCost[grid[i - 1][k]][j] + grid[i][j] for k in range(len(grid[0])))\n",
    "        return min(dfs(len(grid) - 1, j) for j in range(len(grid[0])))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == 0:\n",
    "                return grid[i][j]\n",
    "            return min(dfs(i - 1, k) + moveCost[grid[i - 1][k]][j] + grid[i][j] for k in range(len(grid[0])))\n",
    "        return min(dfs(len(grid) - 1, j) for j in range(len(grid[0])))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
